Сортирање
Због својих примена, сортирање је један од најзначајнијих и најпроучаванијих проблема у рачунарству. Током година развијен је велики број алгоритама за сортирање. Најпознатији су QuickSort, MergeSort, HeapSort, SelectionSort, InsertionSort, BubbleSort и ShellSort. Неки од њих су једноставнији, али спорије раде (такви су Selection, Insertion и Bubble), док су неки ефикаснији, али компликованији за разумевање и реализацију (такви су Quick, Merge, Heap и Shell). Њихова ручна имплементација поучна је као одличан пример за приказ различитих техника конструкције алгоритама.
Ипак, по правилу све библиотеке савремених (а и старијих) програмских језика нуде готове функције за сортирање низова. Коришћење ових функција је увек пожељнија опција у односу на ручну имплементацију (добијају се краћи и разумљивији програми, функције су пажљиво тестиране и скоро извесно потпуно коректне, и имплементиране су на најефикаснији могући начин). Можемо слободно претпоставити да је сложеност и најгорег и просечног случаја код библиотечких функција сортирања квазилинеарна тј. једнака \(O(n \log{n})\) - у делу посвећеном рекурзији и техници “подели па владај”, биће приказани најзначајнији алгоритми сортирања (који се користе и у библиотечким функцијама сортирања) и њихова анализа сложености.
У наставку овог поглавља кроз неколико веома елементарних примера ћемо приказати употребу библиотечких функција сортирања, као и пар елементарних алгоритама сортирања (који се једноставно имплементирају, али су квадратне сложености и стога их никада у пракси не треба употребљавати).
Сортирање подразумева да се елементи ређају у односу на неки поредак. Бројеви се подразумевано ређају по њиховој нумеричкој вредности, ниске се подразумевано ређају лексикографски абецедно (као у речнику), парови и торке се поново ређају лексикографски, по својим компонентама, међутим, често је потребно сортирати низове елемената над којима није дефинисан подразумевани поредак (на пример, низове структура). Библиотечке функције сортирања допуштају навођење различитих критеријума сортирања (задавањем функција поређења), што ће такође бити илустровано кроз неколико елементарних задатака.
Након тога, приказаћемо употребу сортирања као технике претпроцесирања која омогућава да се снизи сложеност решења задатака. Сортирање је толико корисна техника, да у свету конструкције алгоритама често важи правило “Ако не знаш одакле да кренеш да конструишеш алгоритам, ти прво покушај да сортираш податке”. Једна од најзначајнијих примена сортирања је то што се сортирани подаци могу брзо претраживати (применом алгоритма бинарне претраге). Стога ће у наредном поглављу посебна пажња бити посвећена управо томе.